//给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。 
//
// 返回满足此条件的 任一数组 作为答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,1,2,4]
//输出：[2,4,3,1]
//解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5000 
// 0 <= nums[i] <= 5000 
// 
// Related Topics 数组 双指针 排序 
// 👍 248 👎 0

package com.cute.leetcode.editor.cn;
public class SortArrayByParity {
    public static void main(String[] args) {
        Solution solution = new SortArrayByParity().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 奇偶数组，偶数在前，奇数在后
         * 使用两个下标保存奇数和偶数位置，如果偶数在奇数前需要将偶数向后移动
         */
        public int[] sortArrayByParity1(int[] nums) {
            int temp, odd = 0, even = 0;
            int n = nums.length;
            while (odd < n && even < n){
                while (odd < n && (nums[odd] & 1) == 0) odd++;
                while (even < n && (nums[even] & 1) == 1) even++;
                if (odd > even) {
                    even++;// TODO 这里一定要错开
                }else if (odd < n && even < n){
                    temp = nums[odd];
                    nums[odd++] = nums[even];
                    nums[even++] = temp;
                }
            }
            return nums;
        }

        /**
         * 应该使用左右指针，左指针找奇数，右指针找偶数
         */
        public int[] sortArrayByParity(int[] nums) {
            int odd = 0, even = nums.length - 1, temp;
            while (odd < even){
                while (odd < nums.length && (nums[odd] & 1) == 0) odd++;
                while (even >= 0 && (nums[even] & 1) == 1) even--;
                if (odd > even) break;
                temp = nums[odd];
                nums[odd] = nums[even];
                nums[even] = temp;
            }
            return nums;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}